package com.algorithms.techniques.graph;

import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.util.Pair;

public class BellManFordShortestPath<V,E extends EdgeCompare> implements SingleSourceShortestPath<V,E> {

	Map<V,V> parentOfVertex=null;
	Map<V,E> distance=null;
	private  MyEdge INFINITY = new MyEdge(new Double(999),new Double(999));
	private  MyEdge ZERO = new MyEdge(new Double(0),new Double(0));
	public Graph<V, E> createShortestPath(Graph<V, E> graph, V vertex) {
		//Initiatialize the  parents of all vertex
		Graph<V, E> shortestPath =  new DirectedSparseMultigraph<V, E>();
		parentOfVertex = new HashMap<V,V>();
		distance =  new HashMap<V,E>();
		for(V vx :graph.getVertices())
		{
			parentOfVertex.put(vx, null);
			distance.put(vx, (E) INFINITY);
		}
		//printData(graph);
		distance.put(vertex, (E) ZERO);
		int totalVertices =graph.getVertexCount();
		Collection<E> collection = graph.getEdges(); 
		for(int i=0 ;i <totalVertices;i++)
		{
			for(E edge :collection)
			{
				Pair<V> pair=graph.getEndpoints(edge);
				V v1 =pair.getFirst();
				V v2 =pair.getSecond();
				E eV2= distance.get(v2);
				E eV1 = distance.get(v1);
				Double  edgeWeights =eV1.getWeight()+ edge.getWeight();
				if(edgeWeights < eV2.getWeight())
				{
					E newEdgeV2=null;
					try
					{
						newEdgeV2 = (E) eV2.getClass().cast(eV2.clone());
					} catch (CloneNotSupportedException e)
					{
						e.printStackTrace();
					}
					distance.put(v2, newEdgeV2 );
					printData(graph);
					parentOfVertex.put(v2,v1);
				}
			}
			//printData(graph);
		}
		//Create a spanning tree with the  parent of all the vertices
		for (Entry<V, V> entry : parentOfVertex.entrySet())
		{
			V vert = entry.getKey();
			V vertParent = entry.getValue();
			E edge = graph.findEdge(vertParent, vert);
			if (edge != null)
				shortestPath.addEdge(edge, vertParent,
						vert);
		}
		return shortestPath;
	}
   private void printData(Graph<V, E> graph)
   {
	   for(V vx :graph.getVertices())
		{
			System.out.println(vx + " " + distance.get(vx));
			
		}
   }
}
